Codeforces Round #815 (Div. 2)

A

弱智题,交叉相乘判一下倍数关系即可。

Code

#include <cstdio>

long long T, a, b, c, d;

int main() {
    scanf("%lld", &T);
    while (T--) {
        scanf("%lld%lld%lld%lld", &a, &b, &c, &d);
        a *= d, b *= c;
        if (a == b) puts("0");
        else if (a == 0 || b == 0) puts("1");
        else if (a < b) {
            if (b % a == 0) puts("1");
            else puts("2");
        } else {
            if (a % b == 0) puts("1");
            else puts("2");
        }
    }
}

B

记录整个数组的最大值 aa ,次大值 bb ,最小值 cc ,次小值 dd 。容易找到一种划分 (l,r)(l,r) 使得答案为 a+bcda+b-c-d 。显然这是最优的答案。

Code

#include <cstdio>

const int N = 1e5 + 5;

int T, mx1, mx2, mn1, mn2, n, a;

int main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        mx1 = mx2 = 0;
        mn1 = mn2 = 2e9;
        for (int i = 1; i <= n; i++) {
            scanf("%d", &a);
            if (a > mx1) mx2 = mx1, mx1 = a;
            else if (a > mx2) mx2 = a;
            if (a < mn1) mn2 = mn1, mn1 = a;
            else if (a < mn2) mn2 = a;
        }
        printf("%lld\n", 1LL * (mx1 + mx2 - mn1 - mn2));
    }
}

C

注意到在一个满足要求的L形里面,有 22 个格子是 00 是最优的消除方式 ,而消除过后又会产生一个新的L形满足要求。

于是我们便可以找到一个有 2200 的L形,从这里开始不断消除,如果找不到只能浪费一些 11

整个方格表扫一遍即可,时间复杂度 O(nm)O(nm)

Code

#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;

const int N = 505;

int a[N][N], n, m, sum, mn, T;

int main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d", &n, &m);
        sum = 0;
        memset(a, 0, sizeof(a));
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++) {
                scanf("%1d", &a[i][j]);
                sum += a[i][j];
            }
        mn = 0x7fffffff;
        for (int i = 1; i < n; i++)
            for (int j = 1; j < m; j++) {
                int cnt = a[i][j] + a[i][j + 1] + a[i + 1][j] + a[i + 1][j + 1];
                if (cnt) mn = min(mn, max(1, cnt - 1));
            }
        if (sum == 0) puts("0");
        else printf("%d\n", 1 + sum - mn);
    }
}

D1

考虑dp。设 fif_i 为以 ii 结尾的最长的合法子序列长度,则有

fi=maxj<i,aji<aij{fj+1}f_i=\max\limits_{j<i,\,a_j\oplus i\lt a_i\oplus j}\{f_j+1\}

朴素转移时间复杂度 O(n2)O(n^2) ,过不去,怎么办?

考虑缩小 jj 的枚举范围。注意到当 i>j+28i>j+2^8 时,在不考虑二进制下最后 88 位的情况下同样有 i>ji>j

由于 ai200a_i\le 200 ,所以在 aji<aija_j\oplus i<a_i\oplus jaia_i 只会对最后 88 位造成影响,所以 i>j+28i>j+2^8 不会成立,故只需从 i28i-2^8 枚举即可。

时间复杂度降至 O(28n)O(2^8n) ,可以通过 D1 。

Code

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 3e5 + 5;

inline int read() {
	register int x = 0, f = 1;
	char ch = getchar();
	while (ch < '0' || ch > '9') {
		if (ch == '-') f = -f;
		ch = getchar();
	}
	while ('0' <= ch && ch <= '9') {
		x = x * 10 + ch - '0';
		ch = getchar();
	}
	return f == -1 ? -x : x;
}

int a[N], dp[N], n, ans, T;

int main() {
    T = read();
    while (T--) {
        n = read();
        for (int i = 0; i < n; i++) a[i] = read();
        ans = 0;
        for (int i = 0; i < n; i++) {
            dp[i] = 1;
            for (int j = max(i - 255, 0); j < i; j++) {
                if ((a[j] ^ i) < (a[i] ^ j))
                    dp[i] = max(dp[i], dp[j] + 1);
            }
            ans = max(ans, dp[i]);
        }
        printf("%d\n", ans);
    }
}

D2

待补。

E

待补。

赞赏